#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/08/18
# @Author   :Changshu
# @File     :practice_70.py

# 70. 爬楼梯

'''动态规划 f(x)=f(x-1)+f(x-2)'''

def climbStairs(n: int) -> int:
	if n==1:
		return 1
	if n==2:
		return 2
	p=1
	q=2
	s=0
	for i in range(3,n+1):
		s=p+q
		p=q
		q=s
	return s

if __name__ == '__main__':
	n=38
	print(climbStairs(n))